//兑换零钱
public class CoinsExchange {
}
class CoinsExchangeSolution {

    //最少兑换钱数
    public int LessCoins(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n][amount+1];
        for(int i=1;i<=amount;i++){
            dp[0][i] = i%coins[0]==0?i/coins[0]:Integer.MAX_VALUE;
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<=amount;j++){
                dp[i][j] = Integer.MAX_VALUE;
                for(int k=0;k<=j/coins[i];k++){
                    if(dp[i-1][j-k*coins[i]]!=Integer.MAX_VALUE)
                        dp[i][j] = Math.min(dp[i][j],dp[i-1][j-k*coins[i]]+k);
                }
            }
        }
        return dp[n-1][amount]==Integer.MAX_VALUE?-1:dp[n-1][amount];
    }

    //最大兑换种数
    public int MaxWays(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n][amount+1];
        for(int i=0;i<n;i++)
            dp[i][0] = 1;
        for(int i=1;i<=amount;i++){
            dp[0][i] = i%coins[0]==0?1:0;
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<=amount;j++){
                for(int k=0;k<=j/coins[i];k++){
                    dp[i][j] += dp[i-1][j-k*coins[i]];
                }
            }
        }
        return dp[n-1][amount];
    }
}